package LearnDataStructure.a_线性结构.例题;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-03 14:28
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.a_线性结构.例题
 *  * 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前
 *  给定一个链表的头指针 ListNode* pHead，请返回重新排列后的链表的头指针。
 *  注意：分割以后保持原来的数据顺序不变。
 *  不要开辟新的空间，即不要新建节点
 */
public class d_按大小分割单向链表并保持稳定性 {
    public static void main(String[] args) {
        d_按大小分割单向链表并保持稳定性 test = new d_按大小分割单向链表并保持稳定性();
        int[] arr = new int[]{9, 8, 7, 6, 6, 4, 2, 11, 11, 3, 4};
        test.usePartitionLinkedList(arr,6);
    }

    public void usePartitionLinkedList(int[] arr, int x) {
        if (arr.length == 0) {
            System.out.println("输入数据有误");
            return;
        }
        CaseNode head = new CaseNode(arr[0]);
        CaseNode p = head;
        for (int i = 1; i < arr.length; i++) {
            p.next = new CaseNode(arr[i]);
            p = p.next;
        }
        CaseNode result = partitionLinkedList(head, x);
        while (result != null) {
            System.out.println(result.data);
            result = result.next;
        }
    }

    public CaseNode partitionLinkedList(CaseNode head, int x) {
        CaseNode lHead = null;
        CaseNode lTail = null;
        CaseNode rHead = null;
        CaseNode rTail = null;
        CaseNode p = head;
        while (p != null) {
            int value = (int)p.data;
            if (value < x) {
                if (lHead == null) {
                    lHead = p;
                    lTail = p;
                } else {
                    lTail.next = p;
                    lTail = p;
                }

            } else {
                if (rHead == null) {
                    rHead = p;
                    rTail = p;
                } else {
                    rTail.next = p;
                    rTail = p;
                }

            }
            p = p.next;
        }
        if (rTail != null) {
            rTail.next = null;//防止链表成环
        }
        if (lTail != null) {
            lTail.next = rHead;
            return lHead;
        }
        return rHead;
    }
}
